package com.zhanghp.class05;

import com.zhanghp.refer.TreeNode;

import java.util.Arrays;
import java.util.HashMap;

/**
 * <h1>给定先序和中序，生成二叉树</h1>
 * <a href = "https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/">leetcode</a>
 * <hr/>
 * <p>
 * 举例：
 *     <ul>
 *         <li>先序：[3,9,20,15,7]</li>
 *         <li>中序：[9,3,15,20,7]</li>
 *     </ul>
 * 条件：
 *     <ol>
 *         <li>先序/中序均无重复元素</li>
 *         <li>先序和中序长度一样</li>
 *         <li>先序的元素均出现在中序中</li>
 *         <li>preorder保证为二叉树的前序遍历</li>
 *         <li>inorder保证为二叉树的中序遍历</li>
 *     </ol>
 * </p>
 *
 * @author zhanghp
 * @since 2024/1/9 16:27
 */
public class Code05_ConstructBinaryTreeFromPreOrderAndInOrderTraversal {

    public static void main(String[] args) {
        int[] preorder = {1,4,2,3};
        int[] inorder = {1,2,3,4};
        TreeNode treeNode = buildTree(preorder, inorder);
    }

    /**
     * <p>根据先序和中序构建二叉树</p>
     * <p>
     *     复杂度：O(n)
     *     <br/>
     *     每次进行调用gen函数，都是O(1)，调用n次所以是O(n)
     * </p>
     * <hr/>
     * <h2>解析</h2>
     * <p>
     *     先序：[1,2,3,4,5,6,7]
     *     中序：[3,2,4,1,6,5,7]
     * </p>
     * <p>
     *     解析递归gen函数：<br/>
     *     先找到头节点，然后找到中序的头节点，以此分组：<br/>
     *     <ul>
     *         先序 [1] [2,3,4] [5,6,7]
     *         <li>
     *             头节点：[1]
     *         </li>
     *         <li>
     *             左节点：[2,3,4]
     *         </li>
     *         <li>
     *             右节点：[5,6,7]
     *         </li>
     *     </ul>
     *     <ul>
     *         中序 [3,2,4] [1] [6,5,7]
     *         <li>
     *             左节点：[3,2,4]
     *         </li>
     *         <li>
     *             头节点：[1]
     *         </li>
     *         <li>
     *             右节点：[5,6,7]
     *         </li>
     *     </ul>
     *     将先序和中序的<font color = "red">左节点递归</font>：[2,3,4] [3,2,4]<br/>
     *     将先序和中序的<font color = "red">右节点递归</font>：[5,6,7] [6,5,7]<br/>
     *     以此往复，直到初始位置和末位置相等，达到最大深度，进行赋值
     * </p>
     *
     * @param preorder 先序
     * @param inorder 中序
     * @return 二叉树头节点
     */
    public static TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || inorder == null) {
            return null;
        }
        return gen(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
    }

    /**
     * <p>递归：返回头节点信息</p>
     * <p>
     *     为什么只判断L1和R1：<br/>
     *     因为先序和中序的二叉树是一样的，所以取值是相同的
     * </p>
     *
     * @param preorder 先序数组
     * @param L1 先序数组初始位置
     * @param R1 先序数组末位置
     * @param inorder 中序数组
     * @param L2 中序数组初始位置
     * @param R2 中序数组末位置
     * @return 头节点
     */
    public static TreeNode gen(int[] preorder, int L1, int R1, int[] inorder, int L2, int R2){
        // 边界条件
        if (L1 > R1) {
            return null;
        }
        TreeNode head = new TreeNode(preorder[L1]);
        // 相等说明无左右子节点，到这个节点的最大深度了，返回该值
        if (L1 == R1) {
            return head;
        }
        int find = L2;
        // 通过先序的头，来找中序的头在哪个位置
        for(;inorder[find] != preorder[L1]; find ++);
        // 递归
        head.left = gen(preorder, L1 +1, L1 + find - L2, inorder, L2, find - 1);
        head.right = gen(preorder, L1 + find -L2 + 1, R1, inorder, find + 1, R2);

        return head;
    }

    /**
     * <pre>利用空间换时间</pre>
     * <p>根据先序和中序构建二叉树</p>
     * <p>
     *     复杂度：O(n)
     *     <br/>
     *     每次进行调用gen函数，都是O(1)，调用n次所以是O(n)
     * </p>
     *
     * @param preorder 先序
     * @param inorder 中序
     * @return 二叉树头节点
     */
    public static TreeNode buildTree2(int[] preorder, int[] inorder) {
        if (preorder == null || inorder == null) {
            return null;
        }
        HashMap<Integer, Integer> inorderValueMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            inorderValueMap.put(inorder[i], i);
        }
        return gen2(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1, inorderValueMap);
    }

    /**
     * <p>递归：返回头节点信息</p>
     *
     * @param preorder 先序数组
     * @param L1 先序数组初始位置
     * @param R1 先序数组末位置
     * @param inorder 中序数组
     * @param L2 中序数组初始位置
     * @param R2 中序数组末位置
     * @return 头节点
     */
    public static TreeNode gen2(int[] preorder, int L1, int R1, int[] inorder, int L2, int R2, HashMap<Integer, Integer> inorderValueMap){
        // 边界条件
        if (L1 > R1) {
            return null;
        }
        TreeNode head = new TreeNode(preorder[L1]);
        // 相等说明无左右子节点，到这个节点的最大深度了，返回该值
        if (L1 == R1) {
            return head;
        }
        // 通过先序的头，来找中序的头在哪个位置
        int find = inorderValueMap.get(preorder[L1]);
        // 递归
        head.left = gen2(preorder, L1 +1, L1 + find - L2, inorder, L2, find - 1, inorderValueMap);
        head.right = gen2(preorder, L1 + find -L2 + 1, R1, inorder, find + 1, R2, inorderValueMap);

        return head;
    }
}
